Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest Chrome, Safari or Firefox browser.

\( \newcommand{\IN}{\mathbb{N}} \newcommand{\INs}{\mathbb{N}^\ast} \newcommand{\INo}{\mathbb{N}_0} \newcommand{\IZ}{\mathbb{Z}} \newcommand{\IRnn}{\IR_{\geq 0}} \newcommand{\IRsp}{\IR_{\gt 0}} \newcommand{\IR}{\mathbb{R}} \newcommand{\IC}{\mathbb{C}} \newcommand{\A}{\mathcal{A}} \newcommand{\B}{\mathcal{B}} \newcommand{\U}{\mathfrak{U}} \newcommand{\coloneqq}{:=} \newcommand{\coloniff}{:\iff} \newcommand{\Set}[1]{\left\{#1\right\}} \newcommand{\SMid}{\,\middle|\,} \newcommand{\set}[1]{\{#1\}} \newcommand{\smid}{\,|\,} \newcommand{\PSet}[1]{2^{#1}} \newcommand{\supp}{\mathrm{supp}} \newcommand{\dist}[2]{\mathrm{dist}^c_{#1}(#2)} \newcommand{\dists}[2]{{\mathrm{dist}^c_{#1}}'(#2)} \newcommand{\Ind}{{\Large\raise{0pt}{\unicode{x1D7D9}}\,}} \newcommand{\bigO}{\mathcal{O}} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\scalar}[2]{\left\langle #1,#2 \right\rangle} \newcommand{\rDeriv}{\partial_+} \newcommand{\lDeriv}{\partial_-} \newcommand{\queue}{q} \newcommand{\Pc}{\mathcal{P}} \newcommand{\Wc}{\mathcal{W}} \newcommand{\diff}{\mathrm{d}} \newcommand{\eps}{\varepsilon} \newcommand{\ql}[1][e]{Q_{#1}} \newcommand{\fvals}[1]{\mathrm{value}(#1)} \newcommand{\fval}[1]{\mathrm{value}(#1)} \newcommand{\ccaps}[1]{\mathrm{capacity}(#1)} \newcommand{\fcosts}[1]{\mathrm{cost}(#1)} \newcommand{\edgesFrom}[1]{\delta^+(#1)} \newcommand{\edgesTo}[1]{\delta^-(#1)} \newcommand{\PathSet}{\mathcal{P}} \newcommand{\CycleSet}{\mathcal{C}} \)
$(x_e) \in \IR^E$ (edge-based) $s$,$t$-flow:
  • $0 \leq x_e \leq \nu_e$ for all $e \in E$
  • $\sum_{e \in \edgesTo{v}}x_e = \sum_{e \in \edgesFrom{v}}x_e$ for all $v \in V\setminus\Set{s,t}$
  • $\mathrm{value}(x)\coloneqq \sum_{e \in \edgesTo{t}}x_e - \sum_{e \in \edgesFrom{t}}x_e \geq 0$
$(x_p) \in \IR^{\PathSet\cup\CycleSet}$ path-cycle-based $s$,$t$-flow:
  • $0 \leq x_p$ for all $p \in \PathSet\cup\CycleSet$
  • $\mathrm{value}(x)\coloneqq \sum_{p \in \PathSet}x_p$
$(x_e) \in \IR^E$ network-loading of $(x_p) \in \IR^{\PathSet\cup\CycleSet}$ and $(x_p)$ path-cycle-decomposition of $(x_e)$ if $x_e = \sum_{p \in \PathSet\cup\CycleSet: e \in p}x_p$ f.a. $e \in E$
Lemma 2.5: $(x_p) \in \IR^{\PathSet\cup\CycleSet}$ path-cycle-based $s$,$t$-flow. Then, $(x_e) \in \IR^E$ defined by $x_e \coloneqq \sum_{p \in \PathSet\cup\CycleSet: e \in p}x_p$
Lemma 2.5: is non-negative flow, satisfies flow conservation at all nodes $v \in V \setminus \set{s,t}$ and has same value as $(x_p)$.
Lemma 2.6: $(x_e) \in \IR^E$ feasible $s$,$t$-flow. Then, there exists path-cycle-decomposition $(x_p) \in \IR^{\PathSet\cup\CycleSet}$ of $(x_e)$ such that
Lemma 2.5:mm $\fvals{(x_p)} = \fvals{(x_p)}$ and $\abs{\supp((x_e))} \leq \abs{\supp((x_e))}$
Lemma 2.6: Moreover, there exists path-based $s$,$t$-flow $(y_p) \in \IR^{\PathSet}$ such that
Lemma 2.5:mm $\fvals{(y_p)} = \fvals{(x_p)}$ and $y_e \coloneqq \sum_{p \in \PathSet\cup\CycleSet: e \in p}y_p \leq x_e$ f.a. $e \in E$
Lemma 2.3: $x,y \in \IR^E, \alpha \in \IR, z \coloneqq x+\alpha\cdot y$. Then
  1. $x,y$ satisfy flow cons. at $v$ $\implies$ $z$ satisfies flow cons. at $v$
  2. $x$ $s$,$t$-flow, $y$ satisfies flow cons. at $v \neq s,t$, $\mathrm{value}(x)+\alpha\cdot\mathrm{value}(y)\geq 0$, $0 \leq z \leq \nu$
        $\implies$ $z$ $s$,$t$-flow with $\mathrm{value}(z) = \mathrm{value}(x)+\alpha\cdot\mathrm{value}(y)$
  3. $x$ $s$,$t$-flow, $y = \chi_p$ for $p \in \PathSet$, $\alpha\geq -\mathrm{value}(x)$, $x_e+\alpha \in [0,\nu_e]$ f.a. $e \in p$ $\implies$ $z$ $s$,$t$-flow with $\mathrm{value}(z) = \mathrm{value}(x)+\alpha$
  4. $x$ $s$,$t$-flow, $y = \chi_c$ for $c \in \CycleSet$, $x_e+\alpha \in [0,\nu_e]$ f.a. $e \in c$ $\implies$ $z$ $s$,$t$-flow with $\mathrm{value}(z) = \mathrm{value}(x)$

§2.1 Maximum $s$,$t$-Flows

$(x_e)$ maximum $s$,$t$-flow $\coloniff$ $\forall s$,$t$-flows $(y_e)$: $\fvals{y} \leq \fvals{x}$
Theorem 2.8: For any $s$,$t$-network $N=(G,s,t,\nu)$ there exists a maximum $s$,$t$-flow in $N$.
Extreme Value Theorem: $K$ non-empty, compact, $f: K \to \IR$ continuous
mmmmmmmmmmmmmmmm $\implies$ $\exists x^* \in K: f(x^*) = \sup\Set{f(x) \SMid x \in K}$
  • bidirected graph $G^\leftrightarrow = (V,E^\leftrightarrow)$ with $E^\leftrightarrow \coloneqq E \,\,\dot{\cup}\,\, \set{e^\leftarrow \coloneqq wv \smid e=vw \in E}$
  • residual capacity $\nu_e^x \coloneqq \nu_e-x_e$ and $\nu_{e^\leftarrow}^x \coloneqq x_e$
  • residual graph $G^x = (V,E^x)$ with $E^x \coloneqq \set{e \in E^\leftrightarrow | \nu_e^x \gt 0}$
  • residual network $N^x = (G^x,s,t,\nu^x)$
  • augmenting $x$ along $p$ by $\alpha$ gives $(y_e)$ with $y_e \coloneqq \begin{cases}x_e+\alpha, &e \in p \text{ forward edge}\\x_e-\alpha, &e^\leftarrow \in p \text{ backward edge}\\x_e\end{cases}$
Alg. 1: Ford-Fulkerson Algorithm:
Input: $s$,$t$-network $N$
Output: maximum $s$,$t$-flow $x$ in $N$
  1. Start with $x_e \leftarrow 0$ f.a. $e \in E$
  2. While $\exists x$-augmenting $s$,$t$-path in $N^x$ Do
  3. .. compute $\alpha \leftarrow \min\set{\nu^x_e \smid e \in p}$
  4. .. augment $x$ along $p$ by $\alpha$
Lem. 2.12: $x \in \IRnn^E$ an $s$,$t$-flow, $p \in \PathSet$ an $x$-augmenting path, $\alpha \in \IRnn$ with $\alpha \leq \nu_e^x$ f.a. $e \in E$
Lem. 2.12: Then, augmenting $x$ along $p$ by $\alpha$ gives $s$,$t$-flow with value $\alpha$ more than $x$.
$(x_e) \in \IR^E$ (edge-based) $s$,$t$-flow:
  • $0 \leq x_e \leq \nu_e$ for all $e \in E$
  • $\sum_{e \in \edgesTo{v}}x_e = \sum_{e \in \edgesFrom{v}}x_e$ for all $v \in V\setminus\Set{s,t}$
  • $\mathrm{value}(x)\coloneqq \sum_{e \in \edgesTo{t}}x_e - \sum_{e \in \edgesFrom{t}}x_e \geq 0$
$A \subseteq V$ $s$,$t$-cut $\coloniff$ $s \in A, t \notin A$
    ⇝ has capacity $\ccaps{A} \coloneqq \sum_{e \in \edgesFrom{A}}\nu_e$
Lem. 2.14: For any $s$,$t$-flow $x$ and $s$,$t$-cut $A$ we have
Lem. 2.14: $\fvals{x} = \sum_{e \in \edgesFrom{A}}x_e - \sum_{e \in \edgesTo{A}}x_e \leq \ccaps{A}$.
Thm. 2.15: For any $s$,$t$-flow the following are equivalent:
  1. $x$ is maximum $s$,$t$-flow
  2. $\nexists$ any $x$-augmenting path
  3. $\exists$ $s$,$t$-cut $A$: $\ccaps{A} = \fvals{x}$
Cor. 2.16: For any $s$,$t$-network $N$: $\max_{x\, s,t\text{-flow}}\fvals{x} = \min_{A\, s,t\text{-cut}}\ccaps{A}$   "Max-Flow Min-Cut Theorem"
Theorem 2.17:
Ford-Fulkerson is correct.
Cor. 2.18: For $\nu \in \INo^E$: FF computes integral $s$,$t$-flow $x^*$ and terminates after at most $\fvals{x^*}$ many augmentations.

§2.2 Min-Cost-Flows

$(x_e)$ min-cost-flow $\coloniff$ $\forall s$,$t$-flows $(y_e)$: $\fvals{y} = \fvals{x} \implies \fcosts{y} \geq \fcosts{x}$
Extreme Value Theorem: $K$ non-empty, compact, $f: K \to \IR$ continuous
mmmmmmmmmmmmmmmm $\implies$ $\exists x_* \in K: f(x_*) = \inf\Set{f(x) \SMid x \in K}$
node-labels $\ell_v \coloneqq \inf\set{\gamma_p \smid p \text{ a } s,v\text{-path}}$
Lemma 2.23: For any $N$ with all nodes reachable from $s$, the following are equivalent:
  1. no cycles of negative cost
  2. reduced costs w.r.t. $\ell$ are non-negative
  3. $\exists \pi \in \IR^V: \gamma^\pi \geq 0$
reduced costs wrt. $\pi \in \IR^V$: $\gamma^\pi_{vw} \coloneqq \gamma_{vw} + \pi_v-\pi_w$
Lemma 2.26: $N^x$ without negative cycles and $p$ an efficient $s$,$t$-path.
mmmm Then, augmenting along $p$ does not create negative cycles.
Lemma 2.27: For any $s$,$t$-flow $x$:
mm $x$ min-cost-flow $\iff$ no negative cycles in $N^x$
    Cycle-Cancelling-Algorithm:
Input: $s$,$t$-network $N=(G,s,t,\nu,\gamma)$,
Input: value $v \leq$ min-cut-cap
Output: min-cost-flow $x$ of value $v$ in $N$
(1) Start with any $s$,$t$-flow $x$ of value $v$
(2) While $\exists x$-augmenting cycle $c$ with $\gamma_c \lt 0$ Do
(3) .. augment $x$ along $c$ by $\min\set{\nu^x_e \smid e \in c}$
    Successive-Shortest-Path-Algorithm:
Input: $s$,$t$-network $N=(G,s,t,\nu,\gamma)$ without cycles
Input: of negative cost, value $v \leq$ min-cut-cap
Output: min-cost-flow $x$ of value $v$ in $N$
(1) Start with zero flow $x$
(2) While $\fvals{x} \lt v$ Do
(3) .. compute efficient $s$,$t$-path $p$ in $N^x$
(4) .. augment $x$ along $p$ by $\min\set{v-\fvals{x},\min\set{\nu^x_e \smid e \in c}}$
flow dependent edge cost: $\gamma_e: \IRnn \to \IR$
  →   path-cost $\gamma_p: \IRnn^E \to \IR, (x_e) \mapsto \sum_{e \in p}\gamma_e(x_e)$
Theorem 2.30: The following are equivalent for a path-based flow $(x_p)$:
  1. $(x_p)$ is Wardrop equilibrium, i.e. $x_p \gt 0 \implies \gamma_p(x) \leq \gamma_q(x)$ f.a. $p,q \in \PathSet$
  2. $(x_p)$ satisfies $\sum_{p \in \PathSet}\gamma_p(x)(y_p-x_p) \geq 0$ f.a. $(y_p)$ with same value as $(x_p)$     “path-based variational inequality”
  3. $(x_p)$ satisfies $\sum_{e \in E}\gamma_e(x_e)(y_e-x_e) \geq 0$ f.a. $(y_p)$ with same value as $(x_p)$     “edge-based variational inequality”
  4. $(x_p)$ is optimal solution to $\min \Phi(y) \coloneqq \sum_{e \in E}\int_0^{y_e}\gamma_e(z)dz$ s.t. $(y_p)$ has same value as $(x_p)$
Dynamic Network Flows (SoSe 26), Chapter 2: Static Flows
Lukas Graf (lukas.graf@uni-passau.de)
↑ All Slides